package leetcode.editor.cn;

/**
<p>给你一个字符串 <code>s</code>，找到 <code>s</code> 中最长的回文子串。</p>

<p>如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。</p>

<p>&nbsp;</p>

<p><strong>示例 1：</strong></p>

<pre>
<strong>输入：</strong>s = "babad"
<strong>输出：</strong>"bab"
<strong>解释：</strong>"aba" 同样是符合题意的答案。
</pre>

<p><strong>示例 2：</strong></p>

<pre>
<strong>输入：</strong>s = "cbbd"
<strong>输出：</strong>"bb"
</pre>

<p>&nbsp;</p>

<p><strong>提示：</strong></p>

<ul> 
 <li><code>1 &lt;= s.length &lt;= 1000</code></li> 
 <li><code>s</code> 仅由数字和英文字母组成</li> 
</ul>

<div><div>Related Topics</div><div><li>字符串</li><li>动态规划</li></div></div><br><div><li>👍 6288</li><li>👎 0</li></div>
*/

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0){
            return "";
        }
        char[] strs = s.toCharArray();
        int n = strs.length;
        int maxStart = 0;
        int maxLen = 0;
        for (int i=0; i<n ;i++){
            // 以单个字符为中心扩展
            int len1 = expandAroundCenter(strs, i, i);
            // 以两个相邻字符之间为中心扩展
            int len2 = expandAroundCenter(strs, i, i+1);
            int len = Math.max(len1, len2);
            if (len > maxLen){
                maxStart = i - (len - 1) / 2;
                maxLen = len;
            }
        }
        return s.substring(maxStart, maxStart + maxLen);
    }

    private int expandAroundCenter(char[] strs, int left, int right) {
        int n = strs.length;
        while (left >= 0 && right < n && strs[left] == strs[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
